Квадратичен остатък

Едно естествено число $a\,$ се нарича квадратичен остатък по модул $n\,$ ако

\exists x:\quad x^{2}\equiv a{\pmod {n}}.

Свойства

Квадратични остатъци по модул съставно число

Въпросът затова дали едно число е квадратичен остатък по модул $n\,$ за съставни $n\,$ може да се сведе до частния случай за прости $n\,$ , както твърди следната теорема:

Теорема: Нека $a\,$ и $n\,$ са взаимнопрости, a

n=2^{\alpha _{0}}\prod _{i=1}^{s}p_{i}^{\alpha _{i}}

представлява разлагането на $n\,$ на прости множители. Конгруенцията

x^{2}\equiv a{\pmod {n}}

има решение тогава и само тогава, когато е $a\,$ е квадратичен остатък по модул $p_{i},i=1,2,...,s\,$ и е изпълнено поне едно от условията:

$\alpha _{0}<2\,$ или
$\alpha _{0}=2\,$ и $a\equiv 1{\pmod {4}}\quad$ или
$\alpha _{0}>2\,$ и $a\equiv 1{\pmod {8}}.$

Квадратични остатъци по модул просто число

За частния случай на конгруенции по модул просто число е възприето следното обозначение:

Дефинция: Нека $p\,$ е просто число и $p\nmid a$ . Функцията със стойности:

$\left({\frac {a}{p}}\right)=1$ ако $a\,$ е квадратичен остатък по модул $p\,$ и
$\left({\frac {a}{p}}\right)=-1$ в противен случай,

се нарича символ на Льожандър.

Могат да се докажат следните правила за смятане със символа на Льожандър:

$a\equiv b{\pmod {p}}\quad \Rightarrow \quad \left({\frac {a}{p}}\right)=\left({\frac {b}{p}}\right)$
$\left({\frac {a}{p}}\right)\left({\frac {b}{p}}\right)=\left({\frac {ab}{p}}\right)$
Критерий на Ойлер: